// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/trace_event/heap_profiler_allocation_register.h"

#include <algorithm>

#include "base/trace_event/trace_event_memory_overhead.h"

namespace base {
namespace trace_event {

    AllocationRegister::ConstIterator::ConstIterator(
        const AllocationRegister& alloc_register, AllocationIndex index)
        : register_(alloc_register)
        , index_(index)
    {
    }

    void AllocationRegister::ConstIterator::operator++()
    {
        index_ = register_.allocations_.Next(index_ + 1);
    }

    bool AllocationRegister::ConstIterator::operator!=(
        const ConstIterator& other) const
    {
        return index_ != other.index_;
    }

    AllocationRegister::Allocation
    AllocationRegister::ConstIterator::operator*() const
    {
        return register_.GetAllocation(index_);
    }

    size_t AllocationRegister::BacktraceHasher::operator()(
        const Backtrace& backtrace) const
    {
        const size_t kSampleLength = 10;

        uintptr_t total_value = 0;

        size_t head_end = std::min(backtrace.frame_count, kSampleLength);
        for (size_t i = 0; i != head_end; ++i) {
            total_value += reinterpret_cast<uintptr_t>(backtrace.frames[i].value);
        }

        size_t tail_start = backtrace.frame_count - std::min(backtrace.frame_count - head_end, kSampleLength);
        for (size_t i = tail_start; i != backtrace.frame_count; ++i) {
            total_value += reinterpret_cast<uintptr_t>(backtrace.frames[i].value);
        }

        total_value += backtrace.frame_count;

        // These magic constants give best results in terms of average collisions
        // per backtrace. They were found by replaying real backtraces from Linux
        // and Android against different hash functions.
        return (total_value * 131101) >> 14;
    }

    size_t AllocationRegister::AddressHasher::operator()(
        const void* address) const
    {
        // The multiplicative hashing scheme from [Knuth 1998]. The value of |a| has
        // been chosen carefully based on measurements with real-word data (addresses
        // recorded from a Chrome trace run). It is the first prime after 2^17. For
        // |shift|, 13, 14 and 15 yield good results. These values are tuned to 2^18
        // buckets. Microbenchmarks show that this simple scheme outperforms fancy
        // hashes like Murmur3 by 20 to 40 percent.
        const uintptr_t key = reinterpret_cast<uintptr_t>(address);
        const uintptr_t a = 131101;
        const uintptr_t shift = 14;
        const uintptr_t h = (key * a) >> shift;
        return h;
    }

    AllocationRegister::AllocationRegister()
        : AllocationRegister(kAllocationCapacity, kBacktraceCapacity)
    {
    }

    AllocationRegister::AllocationRegister(size_t allocation_capacity,
        size_t backtrace_capacity)
        : allocations_(allocation_capacity)
        , backtraces_(backtrace_capacity)
    {
    }

    AllocationRegister::~AllocationRegister()
    {
    }

    void AllocationRegister::Insert(const void* address,
        size_t size,
        const AllocationContext& context)
    {
        DCHECK(address != nullptr);
        if (size == 0) {
            return;
        }

        AllocationInfo info = {
            size,
            context.type_name,
            InsertBacktrace(context.backtrace)
        };

        // Try to insert the allocation.
        auto index_and_flag = allocations_.Insert(address, info);
        if (!index_and_flag.second) {
            // |address| is already there - overwrite the allocation info.
            auto& old_info = allocations_.Get(index_and_flag.first).second;
            RemoveBacktrace(old_info.backtrace_index);
            old_info = info;
        }
    }

    void AllocationRegister::Remove(const void* address)
    {
        auto index = allocations_.Find(address);
        if (index == AllocationMap::kInvalidKVIndex) {
            return;
        }

        const AllocationInfo& info = allocations_.Get(index).second;
        RemoveBacktrace(info.backtrace_index);
        allocations_.Remove(index);
    }

    bool AllocationRegister::Get(const void* address,
        Allocation* out_allocation) const
    {
        auto index = allocations_.Find(address);
        if (index == AllocationMap::kInvalidKVIndex) {
            return false;
        }

        if (out_allocation) {
            *out_allocation = GetAllocation(index);
        }
        return true;
    }

    AllocationRegister::ConstIterator AllocationRegister::begin() const
    {
        return ConstIterator(*this, allocations_.Next(0));
    }

    AllocationRegister::ConstIterator AllocationRegister::end() const
    {
        return ConstIterator(*this, AllocationMap::kInvalidKVIndex);
    }

    void AllocationRegister::EstimateTraceMemoryOverhead(
        TraceEventMemoryOverhead* overhead) const
    {
        size_t allocated = sizeof(AllocationRegister);
        size_t resident = sizeof(AllocationRegister)
            + allocations_.EstimateUsedMemory()
            + backtraces_.EstimateUsedMemory();
        overhead->Add("AllocationRegister", allocated, resident);
    }

    AllocationRegister::BacktraceMap::KVIndex AllocationRegister::InsertBacktrace(
        const Backtrace& backtrace)
    {
        auto index = backtraces_.Insert(backtrace, 0).first;
        auto& backtrace_and_count = backtraces_.Get(index);
        backtrace_and_count.second++;
        return index;
    }

    void AllocationRegister::RemoveBacktrace(BacktraceMap::KVIndex index)
    {
        auto& backtrace_and_count = backtraces_.Get(index);
        if (--backtrace_and_count.second == 0) {
            // Backtrace is not referenced anymore - remove it.
            backtraces_.Remove(index);
        }
    }

    AllocationRegister::Allocation AllocationRegister::GetAllocation(
        AllocationMap::KVIndex index) const
    {
        const auto& address_and_info = allocations_.Get(index);
        const auto& backtrace_and_count = backtraces_.Get(
            address_and_info.second.backtrace_index);
        return {
            address_and_info.first,
            address_and_info.second.size,
            AllocationContext(
                backtrace_and_count.first,
                address_and_info.second.type_name)
        };
    }

} // namespace trace_event
} // namespace base
